'''
https://leetcode.cn/problems/subsets-ii/
'''

from typing import List


class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        path = [0] * n
        nums.sort()
        def process(i, size_of_path):
            if i == n:
                ans.append(path[:size_of_path])
            else:
                j = i + 1
                while j < n and nums[j] == nums[i]:
                    j += 1
                process(j, size_of_path)
                for t in range(i, j):
                    path[size_of_path] = nums[i]
                    size_of_path += 1
                    process(j, size_of_path)

        process(0, 0)
        return ans
